package com.zjj.algorithm.learning.leetcode.stack;

import java.util.Arrays;
import java.util.Stack;

/**
 * 402. 移掉 K 位数字
 * 中档题
 * <p>
 * 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
 * 示例 1 ：
 * <p>
 * 输入：num = "1432219", k = 3
 * 输出："1219"
 * 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
 * 示例 2 ：
 * <p>
 * 输入：num = "10200", k = 1
 * 输出："200"
 * 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
 * 示例 3 ：
 * <p>
 * 输入：num = "10", k = 2
 * 输出："0"
 * 解释：从原数字移除所有的数字，剩余为空就是 0 。
 *
 * @author zjj_admin
 * @date 2022/11/17 15:12
 */
public class RemoveKDigits {
    public static void main(String[] args) {

        String num = "1120006030508090011110050602030506446660";
        String res = removeKdigits(num, 20);
        System.out.println("res = " + res);

    }


    /**
     * 时间
     * 29 ms
     * 击败
     * 27.51%
     * 内存
     * 42.6 MB
     * 击败
     * 50.18%
     * 思路：
     * 1、当给定的字符串的长度和给定的 k 的值相等，直接返回 0 即可。
     * 2、从左向右依次遍历，将数据压入到栈中，当存在一个后面的数据比前面的小，就将原来栈中的数据移除，将新的数据推入到栈中。
     * 3、当将所有的数据全部入栈了，但是删除的数据还没有到k，就直接将后面入栈的数据移除即可。
     * 4、将剩下的字符串中前面为 0 的内容删除。
     * 5、按照规定返回即可。
     *
     * @param num
     * @param k
     * @return
     */
    public static String removeKdigits(String num, int k) {
        if (num.length() == k) {
            return "0";
        }
        Stack<Integer> stack = new Stack<>();
        int count = k;
        for (int i = 0; i < num.length(); i++) {
            int item = Integer.parseInt(num.substring(i, i + 1));
            while (stack.size() > 0 && count > 0 && stack.peek() > item) {
                stack.pop();
                count--;
            }
            stack.push(item);
        }
        //在比较极端的情况下，当原来的数据就是在递增排列，就将后面的数据移除即可
        for (int i = 0; i < count; i++) {
            stack.pop();
        }
        Object[] array = stack.toArray();
        //删除数据前面的 0
        StringBuilder res = new StringBuilder();
        boolean isZero = true;
        for (int i = 0; i < array.length; i++) {
            if (isZero && array[i].equals(0)) {
                continue;
            }
            isZero = false;
            res.append(array[i]);
        }
        return "".equals(res.toString()) ? "0" : res.toString();
    }
}
